Day10 Leetcode Array系列---- Contains Duplicate II

本次題目 Contains Duplicate II by JS

如果陣列中有重复數字，且重複數字的索引差值小於等於 K 就是 true，如果没有重複數字或者索引差值大於 K ，就是 false。

nums1 = [1,2,3,1]
k1 = 3
output1= true

nums2 = [1,0,1,1]
k2 = 1
output2= true

nums3 = [1,2,3,1,2,3]
k3 = 2
output3= false

思考路線

1. 先判斷陣列中有無重複元素，拿 contains duplicate 那題的答案來用，如果沒有重複元素直接 return false
2. 接著我會想用 while 迴圈去找
3. 設立一個起始值 start = 0 來挑選陣列中的值
4. 利用題目給的 k值，只要在距離某個元素 k 距離以內的有相等的值就是 true，符合題目要求，陣列中兩個相等的值其索引相減不能大於 ｋ
5. while 迴圈的條件就給 start 小於陣列長度，這樣所以元素都可以查過一輪
6. 設立一個 range = 0 來與 k值相扣，利用這個差值當索引比對從陣列中取出的值是否相等
7. 要讓 start 與 range 變動，如果 k - range != 0 我就讓range 增加，這可以查詢距離 start 取出的值範圍 k 距離內的元素是否與其相等
8. 當 k - range = 0 就代表距離起始值抓出的元素範圍 K 以內都沒有相等的值，這個時候我就要讓 start 前進，並且 range = 0 在查詢一次
9. 當所有元素都輪過一輪後，還是沒有符合條件，就在 function 的最尾端回傳 false

Coding Time

先確定傳入的陣列是否有重複元素，有就繼續做，沒有就回傳 false ，並且來個簡單判斷

function duplicate(ary,k){
    let a = ary.filter( (x,index)=> { return ary.indexOf(x) == index})
    if (ary.length == a.length){
        return false
    }
}

function expect(a,b){
    console.log(a==b)
}

建立起始值 (start) 與範圍 (range) 給 while 迴圈用， while 迴圈的條件就 start < 陣列長度，這樣每個元素都可以檢查

function duplicate(ary,k){
    let a = ary.filter( (x,index)=> { return ary.indexOf(x) == index})
    if (ary.length == a.length){
        return false
    }
    
    let start = 0
    let range = 0
    while(start < ary.length){
        
    }
} 

先寫好 start 與 range 的改變方式，當 k - range != 0 ，我就讓 range 增加，如果 k - range == 0 我就讓 start 增加並且讓 range 歸零

function duplicate(ary,k){
    let a = ary.filter( (x,index)=> { return ary.indexOf(x) == index})
    if (ary.length == a.length){
        return false
    }
    
    let start = 0
    let range = 0
    while(start < ary.length){
        if(k-range != 0){     
            range +=1
        }else{
            range = 0
            start +=1
        }
    }
    return false
} 

最後當 start 取出來的值與 k-range 取出來的值一樣就回傳 true，如果沒有就繼續跑迴圈，如果跑到最後迴圈終止還是沒有結果，回傳 false

記得要把 range += 1 放到判斷值相不相等的 if 中

nums1 = [1,2,3,1]
k1 = 3
output1= true

nums2 = [1,0,1,1]
k2 = 1
output2= true

nums3 = [1,2,3,1,2,3]
k3 = 2
output3= false

function duplicate(ary,k){
    let a = ary.filter( (x,index)=> { return ary.indexOf(x) == index})
    if (ary.length == a.length){
        return false
    }
    let start = 0
    let range = 0
    while(start < ary.length){
        if(k-range != 0){     
            if(ary[start] === ary[k-range]){
                return true
            }else{
                range +=1
            }
        }else{
            range = 0
            start +=1
        }
    }
    return false
} 

function expect(a,b){
    console.log(a==b)
}
expect(duplicate(nums1,k1),output1)
expect(duplicate(nums2,k2),output2)
expect(duplicate(nums3,k3),output3)

結論

這題真的想很久，經過大大點醒，我並不一定要紀錄重複元素的索引，再取出來相扣並且判斷符不符合小於 Ｋ值 的條件，可以直接利用距離該元素 K值範圍內有無相同元素這個想法即可

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty